#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#ifdef __EMSCRIPTEN__
#include <emscripten.h>
#else
#define EMSCRIPTEN_KEEPALIVE
#define EM_JS(ret, name, params, ...) \
    ret name params
#endif

#define MAX_PATH_LENGTH 10000
#define MAX_OPEN_LIST 100000
#define STRAIGHT_COST 10
#define DIAGONAL_COST 14
#define DIRECTION_CHANGE_PENALTY 5  // 转向惩罚

typedef struct Node {
    int x;
    int y;
    int F;
    int G;
    int H;
    struct Node* parent;
    int visited;  // 添加访问标记
    int direction;  // 记录移动方向
} Node;

typedef struct {
    Node* nodes;
    int* grid;
    int width;
    int height;
    int openListCount;
    Node* openList[MAX_OPEN_LIST];
    int maxIterations;  // 添加最大迭代次数限制
} AStar;

// 方向数组：右上和左下优先，左上和右下次之，直线移动
const int directions[8][2] = {
    {1, -1}, {-1, 1}, {1, 1}, {-1, -1},    // 对角线移动优先
    {1, 0}, {0, -1}, {-1, 0}, {0, 1}       // 直线移动次之
};

// 添加日志函数
EM_JS(void, console_log, (const char* str), {
    console.log(UTF8ToString(str));
});

// 在文件开头的函数声明部分添加（在AStar结构体定义之后，其他函数之前）
static int is_valid_move(AStar* astar, int fromX, int fromY, int toX, int toY);

// 添加内存使用统计函数
EMSCRIPTEN_KEEPALIVE
void print_memory_usage() {
    char buffer[256];
    size_t total_memory = emscripten_get_heap_size();
    size_t used_memory = emscripten_get_used_heap_size();
    snprintf(buffer, sizeof(buffer), "wasm内存使用: 总内存=%zu字节, 已用内存=%zu字节, 使用率=%.2f%%", 
        total_memory, used_memory, (float)used_memory/total_memory*100);
    console_log(buffer);
}

// 创建A*实例
EMSCRIPTEN_KEEPALIVE
AStar* create_astar(int width, int height) {
    char buffer[256];
    size_t before_memory = emscripten_get_used_heap_size();
    
    AStar* astar = (AStar*)malloc(sizeof(AStar));
    if (!astar) {
        snprintf(buffer, sizeof(buffer), "wasm内存分配失败: 创建AStar结构体");
        console_log(buffer);
        return NULL;
    }

    astar->width = width;
    astar->height = height;
    astar->grid = (int*)calloc(width * height, sizeof(int));
    astar->nodes = (Node*)calloc(width * height, sizeof(Node));
    astar->openListCount = 0;
    astar->maxIterations = width * height * 4;

    if (!astar->grid || !astar->nodes) {
        snprintf(buffer, sizeof(buffer), "wasm内存分配失败: 创建网格或节点数组");
        console_log(buffer);
        free(astar->grid);
        free(astar->nodes);
        free(astar);
        return NULL;
    }

    size_t after_memory = emscripten_get_used_heap_size();
    snprintf(buffer, sizeof(buffer), "wasm创建地图内存使用: 增加=%zu字节, 总内存=%zu字节", 
        after_memory - before_memory, after_memory);
    console_log(buffer);

    return astar;
}

// 更新网格数据
EMSCRIPTEN_KEEPALIVE
void update_grid(int* newGrid, AStar* astar) {
    memcpy(astar->grid, newGrid, astar->width * astar->height * sizeof(int));
}

// 获取节点索引
static inline int get_node_index(int x, int y, int width) {
    return y * width + x;  // 确保使用行优先顺序
}

// 计算H值（考虑对角线移动）
static inline int calculate_h(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    return DIAGONAL_COST * (dx < dy ? dx : dy) + STRAIGHT_COST * (dx > dy ? dx - dy : dy - dx);
}

// 添加到开放列表
static void add_to_open_list(AStar* astar, Node* node) {
    astar->openList[astar->openListCount++] = node;
}

// 从开放列表中移除
static void remove_from_open_list(AStar* astar, int index) {
    astar->openList[index] = astar->openList[--astar->openListCount];
}

// 查找最小F值的节点
static int find_min_f_node(AStar* astar) {
    int minF = astar->openList[0]->F;
    int minIndex = 0;
    
    for (int i = 1; i < astar->openListCount; i++) {
        if (astar->openList[i]->F < minF) {
            minF = astar->openList[i]->F;
            minIndex = i;
        }
    }
    
    return minIndex;
}

// 检查对角线移动是否可行
static int can_move_diagonally(AStar* astar, int x, int y, int dx, int dy) {
    int newX = x + dx;
    int newY = y + dy;
    
    // char buffer[256];
    // snprintf(buffer, sizeof(buffer), "检查对角线移动: 从(%d, %d)到(%d, %d)", x, y, newX, newY);
    // console_log(buffer);
    
    // 检查目标点是否在边界内且可通行
    if (newX < 0 || newX >= astar->width || 
        newY < 0 || newY >= astar->height ||
        astar->grid[get_node_index(newX, newY, astar->width)] != 0) {
        // console_log("目标点不可通行");
        return 0;
    }
    
    // 检查相邻点的状态
    int straightX = astar->grid[get_node_index(x + dx, y, astar->width)];
    int straightY = astar->grid[get_node_index(x, y + dy, astar->width)];
    
    // snprintf(buffer, sizeof(buffer), "移动检查: X方向状态=%d, Y方向状态=%d", straightX, straightY);
    // console_log(buffer);
    
    // 如果至少有一个相邻点可以通行，就允许对角线移动
    if (straightX == 0 || straightY == 0) {
        return 1;
    }
    
    // console_log("两个相邻点都是障碍物，不允许对角线移动");
    return 0;
}

// 获取方向索引
static int get_direction_index(int dx, int dy) {
    for (int i = 0; i < 8; i++) {
        if (directions[i][0] == dx && directions[i][1] == dy) {
            return i;
        }
    }
    return -1;
}

// 计算方向变化的代价
static int calculate_direction_change_cost(Node* current, int newDirection) {
    if (!current->parent) return 0;
    
    int parentDx = current->x - current->parent->x;
    int parentDy = current->y - current->parent->y;
    int parentDirection = get_direction_index(parentDx, parentDy);
    
    // 如果方向改变，增加惩罚
    return (parentDirection != newDirection) ? DIRECTION_CHANGE_PENALTY : 0;
}

// 将is_valid_move的实现移到can_move_diagonally函数之前
static int is_valid_move(AStar* astar, int fromX, int fromY, int toX, int toY) {
    // 检查边界
    if (toX < 0 || toX >= astar->width || toY < 0 || toY >= astar->height) {
        return 0;
    }
    
    // 检查目标点是否可通行
    if (astar->grid[get_node_index(toX, toY, astar->width)] != 0) {
        return 0;
    }
    
    // 计算移动方向
    int dx = toX - fromX;
    int dy = toY - fromY;
    
    // 如果是直线移动，直接返回true
    if (dx == 0 || dy == 0) {
        return 1;
    }
    
    // 对于对角线移动，只检查目标点是否可达
    return 1;
}

// 查找路径
EMSCRIPTEN_KEEPALIVE
int* find_path(AStar* astar, int startX, int startY, int endX, int endY) {
    char buffer[256];
    size_t before_memory = emscripten_get_used_heap_size();
    
    snprintf(buffer, sizeof(buffer), "wasm寻路开始: 从(%d, %d)到(%d, %d), 当前内存=%zu字节", 
        startX, startY, endX, endY, before_memory);
    console_log(buffer);

    // 重置状态
    astar->openListCount = 0;
    memset(astar->nodes, 0, astar->width * astar->height * sizeof(Node));

    // 检查起点和终点是否有效
    if (startX < 0 || startX >= astar->width || startY < 0 || startY >= astar->height ||
        endX < 0 || endX >= astar->width || endY < 0 || endY >= astar->height) {
        // console_log("坐标超出范围");
        return NULL;
    }

    // 检查起点和终点是否可通行
    if (astar->grid[get_node_index(startX, startY, astar->width)] != 0 ||
        astar->grid[get_node_index(endX, endY, astar->width)] != 0) {
        // console_log("起点或终点不可通行");
        return NULL;
    }

    // char buffer[256];
    // snprintf(buffer, sizeof(buffer), "起点坐标: (%d, %d)", startX, startY);
    // console_log(buffer);
    
    // snprintf(buffer, sizeof(buffer), "终点坐标: (%d, %d)", endX, endY);
    // console_log(buffer);

    // 打印起点周围节点的状态
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) continue; // 跳过中心节点
            int newX = startX + dx;
            int newY = startY + dy;
            if (newX >= 0 && newX < astar->width && newY >= 0 && newY < astar->height) {
                // snprintf(buffer, sizeof(buffer), "周围节点 (%d, %d) 状态: %d", 
                //     newX, newY, astar->grid[get_node_index(newX, newY, astar->width)]);
                // console_log(buffer);
            }
        }
    }

    // 创建起始节点
    int startIndex = get_node_index(startX, startY, astar->width);
    Node* startNode = &astar->nodes[startIndex];
    startNode->x = startX;
    startNode->y = startY;
    startNode->G = 0;
    startNode->H = calculate_h(startX, startY, endX, endY);
    startNode->F = startNode->G + startNode->H;
    startNode->parent = NULL;
    startNode->visited = 1;

    // 添加起始节点到开放列表
    add_to_open_list(astar, startNode);

    int iterations = 0;
    while (astar->openListCount > 0 && iterations < astar->maxIterations) {
        iterations++;
        
        // 获取F值最小的节点
        int currentIndex = find_min_f_node(astar);
        Node* currentNode = astar->openList[currentIndex];

        // 添加调试信息
        if (iterations % 100 == 0) {  // 每100次迭代输出一次，避免输出太多
            // char buffer[256];
            // snprintf(buffer, sizeof(buffer), 
            //     "版本1.1,迭代次数: %d, 当前位置: (%d, %d), 开放列表数量: %d", 
            //     iterations, currentNode->x, currentNode->y, astar->openListCount);
            // console_log(buffer);
        }

        // 到达目标
        if (currentNode->x == endX && currentNode->y == endY) {
            // 构建路径
            int* path = (int*)malloc(MAX_PATH_LENGTH * 2 * sizeof(int));
            int pathLength = 0;
            Node* node = currentNode;

            while (node) {
                if (pathLength >= MAX_PATH_LENGTH) {
                    free(path);
                    return NULL;  // 路径太长
                }
                path[pathLength * 2] = node->x;
                path[pathLength * 2 + 1] = node->y;
                pathLength++;
                node = node->parent;
            }

            // 反转路径
            for (int i = 0; i < pathLength / 2; i++) {
                int tempX = path[i * 2];
                int tempY = path[i * 2 + 1];
                path[i * 2] = path[(pathLength - 1 - i) * 2];
                path[i * 2 + 1] = path[(pathLength - 1 - i) * 2 + 1];
                path[(pathLength - 1 - i) * 2] = tempX;
                path[(pathLength - 1 - i) * 2 + 1] = tempY;
            }

            // 在路径开头存储长度
            int* finalPath = (int*)malloc((pathLength * 2 + 1) * sizeof(int));
            finalPath[0] = pathLength;
            memcpy(finalPath + 1, path, pathLength * 2 * sizeof(int));
            free(path);

            snprintf(buffer, sizeof(buffer), "wasm寻路结束: 成功 - 找到路径");
            console_log(buffer);
            return finalPath;
        }

        // 将当前节点移到关闭列表
        remove_from_open_list(astar, currentIndex);
        currentNode->visited = 2;  // 标记为已访问

        // 检查相邻节点
        for (int i = 0; i < 8; i++) {
            int newX = currentNode->x + directions[i][0];
            int newY = currentNode->y + directions[i][1];
            
            // 使用新的移动检查函数
            if (!is_valid_move(astar, currentNode->x, currentNode->y, newX, newY)) {
                continue;
            }
            
            int newNodeIndex = get_node_index(newX, newY, astar->width);
            
            // 检查是否已访问
            if (astar->nodes[newNodeIndex].visited == 2) {
                continue;
            }
            
            // 计算新的G值
            int directionIndex = i;
            int directionChangeCost = calculate_direction_change_cost(currentNode, directionIndex);
            int newG = currentNode->G + (i < 4 ? DIAGONAL_COST : STRAIGHT_COST) + directionChangeCost;

            Node* neighborNode = &astar->nodes[newNodeIndex];
            
            // 如果是新节点或找到更好的路径
            if (!neighborNode->visited || newG < neighborNode->G) {
                neighborNode->x = newX;
                neighborNode->y = newY;
                neighborNode->G = newG;
                neighborNode->H = calculate_h(newX, newY, endX, endY);
                neighborNode->F = neighborNode->G + neighborNode->H;
                neighborNode->parent = currentNode;
                neighborNode->direction = directionIndex;

                if (!neighborNode->visited) {
                    neighborNode->visited = 1;
                    add_to_open_list(astar, neighborNode);
                }
            }
        }
    }

    // 添加未找到路径的原因
    if (iterations >= astar->maxIterations) {
        snprintf(buffer, sizeof(buffer), "wasm寻路结束: 失败 - 达到最大迭代次数限制");
        console_log(buffer);
    } else if (astar->openListCount == 0) {
        snprintf(buffer, sizeof(buffer), "wasm寻路结束: 失败 - 开放列表为空，无法找到有效路径");
        console_log(buffer);
    } else {
        snprintf(buffer, sizeof(buffer), "wasm寻路结束: 成功 - 找到路径");
        console_log(buffer);
    }

    // 在函数结束前添加内存检查
    size_t after_memory = emscripten_get_used_heap_size();
    snprintf(buffer, sizeof(buffer), "wasm寻路结束: 内存变化=%zu字节, 当前内存=%zu字节", 
        after_memory - before_memory, after_memory);
    console_log(buffer);

    return NULL;
}

// 获取路径长度
EMSCRIPTEN_KEEPALIVE
int get_path_length(int* path) {
    return path ? path[0] : 0;
}

// 获取路径点
EMSCRIPTEN_KEEPALIVE
int get_path_point(int* path, int index, int isX) {
    if (!path || index >= path[0]) return -1;
    return path[1 + index * 2 + (isX ? 0 : 1)];
}

// 清理路径
EMSCRIPTEN_KEEPALIVE
void cleanup_path(int* path) {
    char buffer[256];
    snprintf(buffer, sizeof(buffer), "wasm路径清理执行");
    console_log(buffer);
    free(path);
}

// 清理A*实例
EMSCRIPTEN_KEEPALIVE
void cleanup_astar(AStar* astar) {
    if (astar) {
        char buffer[256];
        size_t before_memory = emscripten_get_used_heap_size();
        
        free(astar->grid);
        free(astar->nodes);
        free(astar);
        
        size_t after_memory = emscripten_get_used_heap_size();
        snprintf(buffer, sizeof(buffer), "wasm清理地图内存: 释放=%zu字节, 剩余内存=%zu字节", 
            before_memory - after_memory, after_memory);
        console_log(buffer);
    }
}

// 内存分配函数
EMSCRIPTEN_KEEPALIVE
void* js_malloc(int size) {
    return malloc(size);
}

// 内存释放函数
EMSCRIPTEN_KEEPALIVE
void js_free(void* ptr) {
    free(ptr);
}

// 设置日志级别
EMSCRIPTEN_KEEPALIVE
void set_log_level(int level) {
    // 实现日志级别设置
    // 这里可以根据需要实现具体的日志功能
} 